#include "lockfree_queue.h"
#include <stdlib.h>

void queue_init(queue_t* queue) {
    node_t* dummy = malloc(sizeof(node_t));
    dummy->next = NULL;
    dummy->data = NULL;
    
    atomic_store(&queue->head, dummy, memory_order_relaxed);
    atomic_store(&queue->tail, dummy, memory_order_relaxed);
}

bool queue_enqueue(queue_t* queue, void* data) {
    node_t* new_node = malloc(sizeof(node_t));
    if (!new_node) return false;
    
    new_node->data = data;
    new_node->next = NULL;
    
    while (1) {
        node_t* tail = atomic_load(&queue->tail, memory_order_acquire);
        node_t* next = atomic_load(&tail->next, memory_order_acquire);
        
        if (tail == atomic_load(&queue->tail, memory_order_acquire)) {
            if (next == NULL) {
                if (atomic_compare_exchange_weak(&tail->next, &next, new_node,
                                              memory_order_release,
                                              memory_order_relaxed)) {
                    atomic_compare_exchange_strong(&queue->tail, &tail, new_node,
                                                memory_order_release,
                                                memory_order_relaxed);
                    return true;
                }
            } else {
                atomic_compare_exchange_strong(&queue->tail, &tail, next,
                                            memory_order_release,
                                            memory_order_relaxed);
            }
        }
    }
}

void* queue_dequeue(queue_t* queue) {
    while (1) {
        node_t* head = atomic_load(&queue->head, memory_order_acquire);
        node_t* tail = atomic_load(&queue->tail, memory_order_acquire);
        node_t* next = atomic_load(&head->next, memory_order_acquire);
        
        if (head == atomic_load(&queue->head, memory_order_acquire)) {
            if (head == tail) {
                if (next == NULL) {
                    return NULL;
                }
                atomic_compare_exchange_strong(&queue->tail, &tail, next,
                                            memory_order_release,
                                            memory_order_relaxed);
            } else {
                void* data = next->data;
                if (atomic_compare_exchange_strong(&queue->head, &head, next,
                                                memory_order_release,
                                                memory_order_relaxed)) {
                    free(head);
                    return data;
                }
            }
        }
    }
}

bool queue_is_empty(queue_t* queue) {
    node_t* head = atomic_load(&queue->head, memory_order_acquire);
    node_t* tail = atomic_load(&queue->tail, memory_order_acquire);
    return head == tail;
} 